// 给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
// 说明：解集不能包含重复的子集。
// 思路，回溯
// 此题和子集的区别在于集合是可以有重复的，需要去重，所以需要排序，还有就是树层去重和树枝去重的理解,和之前组合问题的去重一样
function subsetsWithDup(nums) {
    let result = []
    let path = []
    nums.sort((x, y) => x - y)
    function backtracking(startIndex) {
        if (startIndex > nums.length) {
            return
        }
        result.push([...path])
        for (let i = startIndex; i < nums.length; i++) {
            if (i > startIndex && nums[i] === nums[i-1]) {
                continue
            }           
            path.push(nums[i])
            backtracking(i + 1)
            path.pop() 
        }
    }
    backtracking(0)
    return result
}

console.log(subsetsWithDup([1,2,2]))